public class Solution{
    public static int[] solve(int[] nums, int k){
        int n = nums.length;
        int[] result = new int[3];

        // 存储[0,leftPos[i]]中取得最大分组值的索引
        // 存储[0,rightPos[i]]中取得最大分组值的索引
        int[] leftPos = new int[nums.length];
        int[] rightPos = new int[nums.length];

        // 计算sum，以便求分组的大小
        // sum[i] 表示[0,i)的总和
        int[] sum = new int[nums.length+1];
        sum[0] = 0;
        for (int i = 0 ; i < nums.length ; i++){
            sum[i] = (i == 0 ? nums[i] : sum[i-1]+nums[i]);
        }

        // dp 分别求出左边[0,i]中分组的最大值
        for (int i = k-1, tot = sum[i] ; i < n-2*k ; i++){
            if (sum[i] - sum[i-k] > tot)
            {
                tot = sum[i] - sum[i-k];
                leftPos[i] = i-k+1;
            }
        }
        // dp 分别求出右边[i,n-1]中分组的最大值
        for (int i = n-k, tot = sum[n-1]-sum[n-k-1] ; i >= k ; i--){
            if (sum[i+k-1] - sum[i-1] >= tot){
                tot = sum[i+k-1] - sum[i-1];
                rightPos[i] = i;
            }
        }

        // 遍历中间位置的可能索引，去最大值
        int maxsum = sum[leftPos[k-1]] + sum[2*k-1] - sum[k-1] + 
            sum[rightPos[2*k] + k-1] - sum[rightPos[2*k] - 1];
        for (int middle = k, tot = sum[k+k-1]-sum[k-1]; middle <= n-2*k ; middle++){
            if (maxsum < tot + sum[leftPos[middle-1]] - sum[leftPos[middle-1-k]] + sum[rightPos[middle+k-1+k]] - sum[rightPos[middle+k-1]])
            {
                maxsum = tot + sum[leftPos[middle-1]] - sum[leftPos[middle-1-k]] + sum[rightPos[middle+k-1+k]] - sum[rightPos[middle+k-1]];
                result[0] = leftPos[middle-1];
                result[1] = middle;
                result[2] = rightPos[middle+k];
            }
        }
        return result;
    }
    public static void main(String[] argv){
        int[] data = {1,2,1,2,6,7,5,1};
        int k = 2;
        System.out.println(Solution.solve(data, k));
    }
}
